package pers.qianyu.month_202101.date_20210112;

import org.junit.*;

import java.util.*;
import java.util.stream.*;

/**
 * 127. 单词接龙
 * https://leetcode-cn.com/problems/word-ladder/
 *
 * @author mizzle rain
 * @date 2021-01-11 23:28
 */
public class LadderLength {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int len = wordList.size();
        if (len == 0 || !wordList.contains(endWord)) return 0;
        // 构造哈希表
        wordList.add(beginWord);
        wordList = new ArrayList<>(new HashSet<>(wordList));
        len = wordList.size();
        HashMap<String, List<String>> map = new HashMap<>();
        HashMap<String, Boolean> visited = new HashMap<>();
        for (String w : wordList) {
            map.put(w, new ArrayList<>());
            visited.put(w, Boolean.FALSE);
        }
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                String w1 = wordList.get(i);
                String w2 = wordList.get(j);
                if (cmp(w1, w2)) {
                    map.get(w1).add(w2);
                    map.get(w2).add(w1);
                }
            }
        }
        // 广搜
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        int depth = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String poll = q.poll();
                visited.put(poll, Boolean.TRUE);
                if (poll.equals(endWord)) return depth;
                List<String> list = map.get(poll);
                for (String s : list) if (!visited.get(s)) q.offer(s);
            }
            depth++;
        }
        return 0;
    }

    // 如果两个字符串只有一个字母不同就返回 true
    private boolean cmp(String w1, String w2) {
        int len = w1.length(), count = 0;
        for (int i = 0; i < len; i++) {
            char c1 = w1.charAt(i);
            char c2 = w2.charAt(i);
            if (c1 != c2) count++;
        }
        return count == 1;
    }

    @Test
    public void test1() {
        String start = "hit";
        String end = "cog";
        List<String> wordList = Stream.of("hot", "dot", "dog", "lot", "log", "cog")
                .collect(Collectors.toList());
        int result = new LadderLength().ladderLength(start, end, wordList);
        System.out.println("result = " + result);
    }

    @Test
    public void test2() {
        String start = "hit";
        String end = "cog";
        List<String> wordList = Stream.of("hot", "dot", "dog", "lot", "log")
                .collect(Collectors.toList());
        int result = new LadderLength().ladderLength(start, end, wordList);
        System.out.println("result = " + result);
    }

    @Test
    public void test3() {
        String start = "hit";
        String end = "cog";
        List<String> wordList = Stream.of("hot", "dot", "tog", "cog")
                .collect(Collectors.toList());
        int result = new LadderLength().ladderLength(start, end, wordList);
        System.out.println("result = " + result);
    }
}
